package demo.hw;

/**
 * 单词接龙的规则是：
 * 可用于接龙的单词首字母必须要与前一个单词的尾字母相同；
 * 当存在多个首字母相同的单词时，取长度最长的单词，如果长度也相等，则取字典序最小的单词；已经参与接龙的单词不能重复使用。
 * 现给定一组全部由小写字母组成单词数组，并指定其中的一个单词作为起始单词，进行单词接龙，请输出最长的单词串，单词串是单词拼接而成，中间没有空格。
 * 输入描述
 * ·输入的第一行为一个非负整数，表示起始单词在数组中的索引K,0<=K<N;
 * ·输入的第二行为一个非负整数，表示单词的个数N；
 * 接下来的N行，分别表示单词数组中的单词。
 * 备注：
 * .单词个数N的取值范围为[1,20]；
 * ·单个单词的长度的取值范围为[1,30]：
 * 输出描述
 * 输出一个字符串α，表示最终拼接的单词串。
 * 示例1
 * 输入
 * 0
 * 6
 * word
 * dd
 * da
 * dc
 * dword
 * d
 * 输出：worddwordda
 * 说明：先确定起始单词word,再接以d开头的且长度最长的单词dword,剩余以d开头且长度最长的有dd、da、dc,则取字典序最小的da,所以最后输出worddwordda。
 * <p>
 * 示例2
 * 输入
 * 4
 * 6
 * word
 * dd
 * da
 * dc
 * dword
 * d
 * 输出：dwordda
 * 说明：先确定起始单词dword,剩余以d开头且长度最长的有dd、da、dc,则取字典序最小的da,所以最后输出dwordda。
 * 思路：贪心
 * 贪心算法：每一步都根据规则（首字母匹配、长度最长、字典序最小）选择当前最优的单词，确
 * 保每一步的选择都是局部最优，从而得到最终结果。
 * 模拟过程：按照单词接龙的规则逐步构建单词串，直到没有可接的单词为止。
 */
public class _单词接龙 {
    public static void main(String[] args) {
        String[] words = {"word", "dd", "da", "dc", "dword", "d"};
        int k = 0;
        int l = words.length;
        // worddwordda
        boolean[] used = new boolean[l];
        StringBuilder ans = new StringBuilder();
        ans.append(words[k]);
        used[k] = true;
        while (true) {
            char lastC = ans.charAt(ans.length() - 1);// 上一个单词的尾字母
            int bestIdx = -1;

            for (int i = 0; i < l; i++) {
                if (used[i]) continue;
                String best = words[i];
                if (best.charAt(0) != lastC) continue; // 上一单词结尾==下一单词开头

                if (bestIdx == -1) {
                    bestIdx = i;
                } else {
                    // 比较规则：长度更长 或 长度相等且字典序更小
                    String last = words[bestIdx];
                    if (best.length() > last.length()
                            || (last.length() == best.length() && best.compareTo(last) < 0)) {
                        bestIdx = i;
                    }
                }
            }

            if (bestIdx == -1) break;
            used[bestIdx] = true;
            ans.append(words[bestIdx]);
        }
        System.out.println(ans);
    }
}
